
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class GrafoLista implements Grafo{
	
	private List<Vertice> vertices;
	private List<Aresta> arestas;
	
	GrafoLista(){
		vertices = new ArrayList<Vertice>();
		arestas = new ArrayList<Aresta>();
	}

	public void adicionarAresta(Aresta a){
		Vertice v1, v2;
		v1 = a.getV1();
		v2 = a.getV2();
		v1.adicionarIncidente(a);
		v2.adicionarIncidente(a);
		arestas.add(a);
	}
	
	/*
	public void adicionarAresta(Aresta a) throws ArestaComVerticeInvalidoException {
		if((a.getV1() != null)&&(a.getV2() != null)){
			this.arestas.add(a);	
		}else{
			throw new ArestaComVerticeInvalidoException(a);
		}
	}

	public void adicionarArestaPorCompleto(Aresta a) throws ArestaComVerticeInvalidoException {
		if (!vertices.contains(a.getV1())&&!vertices.contains(a.getV1())){
			adicionarVertice(a.getV1());
			adicionarVertice(a.getV2());
		}
		else if (vertices.contains(a.getV1())){
			adicionarVertice(a.getV2());
		}
		else adicionarVertice(a.getV1());
		adicionarAresta(a);
	}
	*/

	public void adicionarVertice(Vertice v) {
		vertices.add(v);
	}
	
	public void removerAresta(Aresta a) {
		a.getV1().getIncidentes().remove(a);
		a.getV2().getIncidentes().remove(a);
		arestas.remove(a);
	}

	public void removerVertice(Vertice v) {
		arestas.removeAll(v.getIncidentes());
		vertices.remove(v);
	}
	
	public int getNumeroArestas() {
		return arestas.size();
	}

	public int getNumeroVertices() {
		return vertices.size();
	}

	public Aresta getAresta(int id) {
		for (int i = 0; i<getNumeroArestas(); i++){
			if ((arestas.get(i)).getId() == id) return arestas.get(i);
		}
		return null;
	}
	
	public Vertice getVertice(int id) {
		for (int i = 0; i<getNumeroVertices(); i++){
			if ((vertices.get(i)).getId() == id) return vertices.get(i);
		}
		return null;
	}

	public Aresta[] getArestas() {
		Aresta[] Arestas = new Aresta[getNumeroArestas()];
		for (int i = 0; i<getNumeroArestas(); i++){
			Arestas[i] = arestas.get(i);
		}
		return Arestas;
	}
	
	public Vertice[] getVertices() {
		Vertice[] Vertices= new Vertice[getNumeroVertices()];
		for (int i = 0; i<getNumeroVertices(); i++){
			Vertices[i] = vertices.get(i);
		}
		return Vertices;
	}

	public Aresta[] getArestasIncidentes(Vertice v) {
		Aresta[] ArestasI = new Aresta[v.getIncidentes().size()];
		for (int i = 0; i<v.getIncidentes().size(); i++){
			ArestasI[i] = v.getIncidentes().get(i);
		}
		return ArestasI;
	}

	public Vertice[] getVerticesAdjacentes(Vertice v) {
		Aresta[] Incid = getArestasIncidentes(v);
		Vertice[] VerticesA= new Vertice[Incid.length];
		for (int i = 0; i<Incid.length; i++){
			VerticesA[i] = Incid[i].getOposto(v);
		}
		return VerticesA;
	}

	public List<Vertice> percursoLargura(Vertice vo) {
		ArrayList<Vertice> verticesVisitados = new ArrayList<Vertice>();
		Queue<Vertice> filaVertices = new LinkedList<Vertice>();
		filaVertices.add(vo);
		while (!filaVertices.isEmpty()) {
			Vertice vAtual = (Vertice) filaVertices.poll();
			verticesVisitados.add(vAtual);
			List<Vertice> adjacentes = vAtual.getAdjacentes();
			for (Object adjacente : adjacentes) {
				if (!filaVertices.contains(adjacente) &&
					!verticesVisitados.contains(adjacente)) {
						filaVertices.add((Vertice) adjacente);
				}
			}
		}
		return verticesVisitados;
	}

	public void percursoProfundidadeAux (Vertice vo, List<Vertice> l) {
		if (!l.contains(vo)) {
			List<Vertice> adjacentes = vo.getAdjacentes();
			l.add(vo);
			for (Vertice v : adjacentes) {
				percursoProfundidadeAux(v, l);
			}
		}
	}
	
	public List<Vertice> percursoProfundidade (Vertice vo) {
		List<Vertice> verticesVisitados = new ArrayList<Vertice>();
		percursoProfundidadeAux(vo, verticesVisitados);
		return verticesVisitados;
	}

}
